package ca.mcgill.schedulability.singleevent.utils;

import java.util.ArrayList;
import java.util.List;

import ca.mcgill.model.digraph.Digraph;
import ca.mcgill.model.digraph.DigraphEdge;
import ca.mcgill.model.functional.Transition;
import ca.mcgill.model.implementation.Task;
import ca.mcgill.schedulability.singleevent.functional.DemandTuple;
import ca.mcgill.schedulability.singleevent.functional.DemandTupleSet;



// given a set of DTs and a particular time, 
// we use Stigge's algorithm to compute which transitions
// (execution/ demand paths) will be executed within such a
// time interval


// arguments --> time interval t
//			 --> the digraph of current task
//			 --> the demand tuple set


public class dbf {

	
	// this is a point-to-point porting of Stigge's implementation
	// TODO: check how dynamic programming ideas could be applied..!!
	
	public static double dbf(double t, Digraph myDigraph, DemandTupleSet myDTset){
		
		double e_prime, d_prime; 
		double dbf = 0;
		boolean addTakenEdge = false, allTaken = true;
		int DTcounter = 0;
		
		// the demand tuples that we will add within the current step
		List<DemandTuple> DTnewList = new ArrayList<DemandTuple>();
		// the indexes of demand tuples to be removed.
		List<Integer> DTindexes = new ArrayList<Integer>();
		
		// in the case of dbf -- we could use the variable of requested time to store the
		// d variable of Stigge's algorithm. 
		
		for (double k=0;k<t;k++){
			
			DTcounter = 0;
			DTindexes.clear();
			
			// for all demand tuples - line 4 of stigge (fig. 5)
			for (DemandTuple DT : myDTset.getDemandTuples()) {
				
				int outgoingEdgesCounter = 0;
				
				// get the interarrival time for all outgoing edges 
				// and check is that my edge -- like line 5 of stigge
				for (DigraphEdge edge : myDigraph.getEdges()) {
					if (DT.getTransition().equals(edge.getSrcVertex())) {
									
						if (!DT.getTakenEdges().get(outgoingEdgesCounter)){

							// extend the demand path
							Transition toNext = edge.getDstVertex(); 
							Transition current = edge.getSrcVertex();

							// line 6 of stigge
							e_prime = DT.getExecTime() + toNext.getAction().getWCET();
							// line 7 of stigge
							d_prime = DT.getRequestTime() - current.getRelativeDeadline()
									  + edge.getInterArrivalTime() + toNext.getRelativeDeadline();
							
							
							// line 8 
							if (d_prime < t){		
	
								List<Boolean>  TakenEdgesBoolean = new ArrayList<Boolean>();

								// the outgoing edges of toNext transitions should be marked as notTaken
								for (DigraphEdge edge2 : myDigraph.getEdges()) {
									if (toNext.equals(edge2.getSrcVertex())) {
										TakenEdgesBoolean.add(addTakenEdge);
									}
								}
								DemandTuple DTnew = new DemandTuple(e_prime, d_prime , toNext, TakenEdgesBoolean);
								DTnewList.add(DTnew);
								
								
								DT.setTakenEdge(outgoingEdgesCounter, true);
							}	
						}
						outgoingEdgesCounter++;
					}
				} // for all Digraph edges -> find the outgoing ones. 	
				
				
				// check if the current DT has all its edges taken --> you can remove it
				for (boolean outgoingEdges : DT.getTakenEdges()) {
					allTaken = true;
					if (!outgoingEdges){
						allTaken = false;
					}
				}
				
				if (allTaken){
					DTindexes.add(DTcounter);
				}
				
				DTcounter++;
			} // for all DT tuples
			
			
			// update my Demand Tuple set = (1) remove those with all taken edges
			// (2) add newly created and 
			
			
			// (1) remove demand tuples with all edges taken -- no point to check them again
			// do it going backwards not to mess with the indexes
			
			int sizeOfDTindexes = DTindexes.size();
			
			for (int i=sizeOfDTindexes-1;i>=0;i--){
				myDTset.removeDemandTuple(DTindexes.get(i));
			}
			
			
			// (2) add the DTs that you traverse through them in the current step
			// in order to cycle through them in the next step 
			// NB it is the equivalent of DT(k-1)--> DT(k) of stigge
			myDTset.addDemandTupleSet(DTnewList);
					
			// check why it is slow and how many DTs you have per case
			// System.out.println("time step " + k + " DT size " + myDTset.getDemandTuples().size());

		
		}


		// get the max of all DT sets -- line 14 of stigge
		for (DemandTuple DTmax : myDTset.getDemandTuples()) {
			if (dbf < DTmax.getExecTime()){
				dbf = DTmax.getExecTime();
			}
		}
		
		return dbf;	
	}
	
	

	public static double dbfStigge(double t, Digraph myDigraph, DemandTupleSet myDTset){
		
		double e_prime, d_prime; 
		double dbf = 0;
		boolean addTakenEdge = false, allTaken = true;
		int DTcounter = 0;
		
		// the demand tuples that we will add within the current step
		List<DemandTuple> DTnewList = new ArrayList<DemandTuple>();
		// the indexes of demand tuples to be removed.
		List<Integer> DTindexes = new ArrayList<Integer>();
		
		// in the case of dbf -- we could use the variable of requested time to store the
		// d variable of Stigge's algorithm. 
		
		for (double k=0;k<t;k++){
			
			DTcounter = 0;
			DTindexes.clear();
			
			// for all demand tuples - line 4 of stigge (fig. 5)
			for (DemandTuple DT : myDTset.getDemandTuples()) {
				
				int outgoingEdgesCounter = 0;
				
				// get the interarrival time for all outgoing edges 
				// and check is that my edge -- like line 5 of stigge
				for (DigraphEdge edge : myDigraph.getEdges()) {
					if (DT.getTransition().equals(edge.getSrcVertex())) {
									
						if (!DT.getTakenEdges().get(outgoingEdgesCounter)){

							// extend the demand path
							Transition toNext = edge.getDstVertex(); 
							Transition current = edge.getSrcVertex();

							// line 6 of stigge
							e_prime = DT.getExecTime() + toNext.getAction().getWCET();
							// line 7 of stigge
							d_prime = DT.getRequestTime() - current.getRelativeDeadline()
									  + edge.getInterArrivalTime() + toNext.getRelativeDeadline();
							
							
							// line 8 
							if (d_prime < t){		
	
								List<Boolean>  TakenEdgesBoolean = new ArrayList<Boolean>();

								// the outgoing edges of toNext transitions should be marked as notTaken
								for (DigraphEdge edge2 : myDigraph.getEdges()) {
									if (toNext.equals(edge2.getSrcVertex())) {
										TakenEdgesBoolean.add(addTakenEdge);
									}
								}
								DemandTuple DTnew = new DemandTuple(e_prime, d_prime , toNext, TakenEdgesBoolean);
								DTnewList.add(DTnew);
								
								
								DT.setTakenEdge(outgoingEdgesCounter, true);
							}	
						}
						outgoingEdgesCounter++;
					}
				} // for all Digraph edges -> find the outgoing ones. 	
				
				
				// check if the current DT has all its edges taken --> you can remove it
				for (boolean outgoingEdges : DT.getTakenEdges()) {
					allTaken = true;
					if (!outgoingEdges){
						allTaken = false;
					}
				}
				
				if (allTaken){
					DTindexes.add(DTcounter);
				}
				
				DTcounter++;
			} // for all DT tuples
			
			
			// update my Demand Tuple set = (1) remove those with all taken edges
			// (2) add newly created and 
			
			
			// (1) remove demand tuples with all edges taken -- no point to check them again
			// do it going backwards not to mess with the indexes
			
			int sizeOfDTindexes = DTindexes.size();
			
			for (int i=sizeOfDTindexes-1;i>=0;i--){
				myDTset.removeDemandTuple(DTindexes.get(i));
			}
			
			
			// (2) add the DTs that you traverse through them in the current step
			// in order to cycle through them in the next step 
			// NB it is the equivalent of DT(k-1)--> DT(k) of stigge
			myDTset.addDemandTupleSet(DTnewList);
					
			// check why it is slow and how many DTs you have per case
			// System.out.println("time step " + k + " DT size " + myDTset.getDemandTuples().size());

		
		}


		// get the max of all DT sets -- line 14 of stigge
		for (DemandTuple DTmax : myDTset.getDemandTuples()) {
			if (dbf < DTmax.getExecTime()){
				dbf = DTmax.getExecTime();
			}
		}
		
		return dbf;	
	}
	


	
}



// think about that for the dynamic iteration way --> not the k++
// http://stackoverflow.com/questions/993025/java-adding-elements-to-a-collection-during-iteration
